package javaTec;

import java.util.ArrayList;
import java.util.List;
/**
 * Created by yangshunxing on 2017/8/11.
 */
public class TreeNodeSolution {
    /**
     * 二叉树的路径和
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here
        TreeNode node = root;
        List<List<Integer>> pathList = new ArrayList<>();
        List<Integer> nodeList1 = new ArrayList<>();
        if (node==null){
            return pathList;
        }
        nodeList1.add(node.val);
        leftRight(node,nodeList1,pathList);

        List<List<Integer>> result = new ArrayList<>();
        for (int i=0; i<pathList.size(); i++){
            List<Integer> list = pathList.get(i);
            if(sumOfList(list)==target){
                result.add(list);
            }
        }
        return result;
    }

    private int sumOfList(List<Integer> list){
        int sum=0;
        for (Integer integer: list){
            sum+=integer;
        }
        return sum;
    }

    /**
     * @param node 根节点
     * @param nodeList 到根节点为止已经形成的路径
     * @param pathList 存储所有路径结果的结果集
     */
    private void leftRight(TreeNode node, List<Integer> nodeList, List<List<Integer>> pathList) {
        if (node.left==null && node.right==null){
            pathList.add(nodeList);
        }
        if(node.right!=null){                   /**如果右节点不为空*/
            List nodeList2 = new ArrayList();
            nodeList2.addAll(nodeList);        /**把当前节点的路径复制一份*/
            nodeList2.add(node.right.val);      /**加入右节点的值路径*/
            if(node.right.left==null && node.right.right==null){
                pathList.add(nodeList2);        /**如果右节点是个叶子节点，就把这个路径放入结果集*/
            }else{
                leftRight(node.right,nodeList2,pathList); /**如果右节点不是叶子节点，进行下一次递归*/
            }
        }
        if(node.left!=null){
            nodeList.add(node.left.val);       /**遍历的左节点都用参数传进来的list，不新建路径列表（使用参数的节点处理得放在后面，因为处理完之后参数会被改变）*/
            if(node.left.left==null && node.left.right==null){
                pathList.add(nodeList);       /**如果左节点是个叶子节点，就把这个路径放入结果集*/
            }else{
                leftRight(node.left, nodeList,pathList); /**如果左节点不是叶子节点，进行下一次递归*/
            }
        }

    }


    public static void main(String[] args) {
        TreeNodeSolution solution = new TreeNodeSolution();
        TreeNode node8 = new TreeNode(5);
        TreeNode node7 = new TreeNode(6);
        TreeNode node6 = new TreeNode(5);
        TreeNode node5 = new TreeNode(4);
        TreeNode node4 = new TreeNode(3);
        TreeNode node3 = new TreeNode(2);
        TreeNode node2 = new TreeNode(2);
        TreeNode node1 = new TreeNode(1);

        node1.left=node2;
        node1.right=node5;
        node2.left=node3;
        node2.right=node4;
        node5.left=node6;
        node5.right=node7;
        node4.left=node8;

        System.out.println(solution.binaryTreePathSum(node1,10));
    }
}
